/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.*
import java.io.Serializable
import java.lang.NullPointerException
import java.util.*
import kotlin.Comparator

/**
 * Reflected double ended heaps. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * This class implements a general technique which uses two
 * [MergeableAddressableHeap]s to implement a double ended heap, described
 * in detail in the following
 * [paper](http://dx.doi.org/10.1016/S0020-0190(02)00501-X):
 *
 *  * C. Makris, A. Tsakalidis, and K. Tsichlas. Reflected min-max heaps.
 * Information Processing Letters, 86(4), 209--214, 2003.
 *
 *
 *
 *
 * The running time bounds depend on the implementation of the underlying used
 * heap. All the above bounds, however, assume that the user does not perform
 * cascading melds on heaps such as:
 *
 * <pre>
 * d.meld(e);
 * c.meld(d);
 * b.meld(c);
 * a.meld(b);
</pre> *
 *
 * The above scenario, although efficiently supported by using union-find with
 * path compression, invalidates the claimed bounds.
 *
 *
 *
 * Note that the ordering maintained by a this heap, like any heap, and whether
 * or not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the
 * `AddressableHeap` interface. (See `Comparable` or
 * `Comparator` for a precise definition of *consistent with
 * equals*.) This is so because the `AddressableHeap` interface is
 * defined in terms of the `equals` operation, but this heap performs all
 * key comparisons using its `compareTo` (or `compare`) method, so
 * two keys that are deemed equal by this method are, from the standpoint of
 * this heap, equal. The behavior of a heap *is* well-defined even if its
 * ordering is inconsistent with `equals`; it just fails to obey the
 * general contract of the `AddressableHeap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
open class ReflectedHeap<K, V> @JvmOverloads constructor(
    heapFactory: AddressableHeapFactory<K, HandleMap<K,V>,MergeableAddressableHeap<K,HandleMap<K,V>>>,
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    private val comparator: Comparator<in K?>? = null
) : MergeableDoubleEndedAddressableHeap<K, V>, Serializable {

    /**
     * A minimum heap
     */
    private val minHeap:MergeableAddressableHeap<K, HandleMap<K,V>> = heapFactory.get(comparator)

    /**
     * A maximum heap
     */
    private val maxHeap:MergeableAddressableHeap<K, HandleMap<K,V>> = heapFactory.get(Collections.reverseOrder(comparator))

    /**
     * A free element in case the size is odd
     */
    private var free: ReflectedHandle<K, V>?

    /**
     * Size of the heap
     */
    private var size: Long

    /**
     * Used to reference the current heap or some other heap in case of melding,
     * so that handles remain valid even after a meld, without having to iterate
     * over them.
     *
     * In order to avoid maintaining a full-fledged union-find data structure,
     * we disallow a heap to be used in melding more than once. We use however,
     * path-compression in case of cascading melds, that it, a handle moves from
     * one heap to another and then another.
     */
    private var other: ReflectedHeap<K, V>

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     * @param heapFactory
     * a factory for the underlying heap implementation
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     *
     * @throws NullPointerException
     * if the heap factory is null
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys. All
     * keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     * @param heapFactory
     * a factory for the underlying heap implementation
     * @throws NullPointerException
     * if the heap factory is null
     */
    init {
        this.free = null
        this.size = 0
        this.other = this
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    override val isEmpty: Boolean
        get() = size == 0L

    /**
     * {@inheritDoc}
     */
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun clear() {
        size = 0
        free = null
        minHeap.clear()
        maxHeap.clear()
    }

    /**
     * {@inheritDoc}
     */
    override fun insert(key: K, value: V?): ReflectedHandle<K, V> {
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        } else check(other === this) { "A heap cannot be used after a meld" }
            if (size % 2 == 0L) {
                free = ReflectedHandle(this, key, value)
                size++
                return free!!
            } else {
                val newHandle = ReflectedHandle(this, key, value)
                insertPair(newHandle, free!!)
                free = null
                size++
                return newHandle
            }
    }

    /**
     * {@inheritDoc}
     */
   /* override fun insert(key: K?): DoubleE<K, V> {
        return insert(key, null)
    }*/

    /**
     * {@inheritDoc}
     */
    override fun findMin():ReflectedHandle<K, V> {
        if (size == 0L) {
            throw NoSuchElementException()
        } else if (size == 1L) {
            return free!!
        } else if (size % 2 == 0L) {
            return minHeap.findMin().value!!.outer
        } else {
            val minInnerHandle = minHeap.findMin()
            val c = comparator?.compare(minInnerHandle.key, free!!.key)
                ?: (minInnerHandle.key as Comparable<K>?)!!.compareTo(free!!.key)
            return if (c < 0) {
                minInnerHandle.value!!.outer
            } else {
                free!!
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun findMax(): DoubleEndedAddressableHeap.DoubleEndedHandle<K, V> {
        if (size == 0L) {
            throw NoSuchElementException()
        } else if (size == 1L) {
            return free!!
        } else if (size % 2 == 0L) {
            return maxHeap.findMin().value!!.outer
        } else {
            val maxInnerHandle = maxHeap.findMin()
            val c = comparator?.compare(maxInnerHandle.key, free!!.key)
                ?: (maxInnerHandle.key as Comparable<K>?)!!.compareTo(free!!.key)
            return if (c > 0) {
                maxInnerHandle.value!!.outer
            } else {
                free!!
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun deleteMin(): ReflectedHandle<K, V> {
        if (size == 0L) {
            throw NoSuchElementException()
        } else if (size == 1L) {
            val min = free
            free = null
            size--
            return min!!
        } else if (size % 2 == 0L) {
            // find min
            val minInner = minHeap.deleteMin()
            val minOuter = minInner.value!!.outer
            minOuter.inner = null
            minOuter.minNotMax = false

            // delete max and keep as free
            val maxInner = minInner.value!!.otherInner
            val maxOuter = maxInner.value!!.outer
            maxInner.delete()
            maxOuter.inner = null
            maxOuter.minNotMax = false

            free = maxOuter
            size--

            return minOuter
        } else {
            // find min
            val minInner = minHeap.findMin()
            val c = comparator?.compare(minInner.key, free!!.key)
                ?: (minInner.key as Comparable<K>?)!!.compareTo(free!!.key)
            if (c >= 0) {
                val min = free
                free = null
                size--
                return min!!
            }

            // minInner is smaller
            minInner.delete()
            val minOuter = minInner.value!!.outer
            minOuter.inner = null
            minOuter.minNotMax = false

            // delete max
            val maxInner = minInner.value!!.otherInner
            val maxOuter = maxInner.value!!.outer
            maxInner.delete()
            maxOuter.inner = null
            maxOuter.minNotMax = false

            // reinsert max with free
            insertPair(maxOuter, free!!)
            free = null
            size--

            return minOuter
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun deleteMax(): DoubleEndedAddressableHeap.DoubleEndedHandle<K, V> {
        if (size == 0L) {
            throw NoSuchElementException()
        } else if (size == 1L) {
            val max = free
            free = null
            size--
            return max!!
        } else if (size % 2 == 0L) {
            // find max
            val maxInner = maxHeap.deleteMin()
            val maxOuter = maxInner.value!!.outer
            maxOuter.inner = null
            maxOuter.minNotMax = false

            // delete min and keep as free
            val minInner = maxInner.value!!.otherInner
            val minOuter = minInner.value!!.outer
            minInner.delete()
            minOuter.inner = null
            minOuter.minNotMax = false

            free = minOuter
            size--

            return maxOuter
        } else {
            // find max
            val maxInner = maxHeap.findMin()
            val c = comparator?.compare(maxInner.key, free!!.key)
                ?: (maxInner.key as Comparable<K>?)!!.compareTo(free!!.key)
            if (c < 0) {
                val max = free
                free = null
                size--
                return max!!
            }

            // maxInner is larger
            maxInner.delete()
            val maxOuter = maxInner.value!!.outer
            maxOuter.inner = null
            maxOuter.minNotMax = false

            // delete min
            val minInner = maxInner.value!!.otherInner
            val minOuter = minInner.value!!.outer
            minInner.delete()
            minOuter.inner = null
            minOuter.minNotMax = false

            // reinsert min with free
            insertPair(minOuter, free!!)
            free = null
            size--

            return maxOuter
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun meld(other: MergeableDoubleEndedAddressableHeap<K, V>) {
        check(other is ReflectedHeap<K,V>){"A heap must ReflectedHeap"}
        val h = other

        // check same comparator
        if (comparator != null) {
            require(!(h.comparator() == null || h.comparator() != comparator)) { "Cannot meld heaps using different comparators!" }
        } else require(h.comparator() == null) { "Cannot meld heaps using different comparators!" }

        check(h.other === h) { "A heap cannot be used after a meld." }

        //require(minHeap is MergeableAddressableHeap<*, *>) { "Underlying heaps are not meldable." }

        // meld min heaps
        val minAsMergeableHeap = minHeap
        val hMinAsMergeableHeap = h.minHeap
        minAsMergeableHeap.meld(hMinAsMergeableHeap)

        // meld max heaps
        val maxAsMergeableHeap = maxHeap
        val hMaxAsMergeableHeap = h.maxHeap
        maxAsMergeableHeap.meld(hMaxAsMergeableHeap)

        // meld free
        if (free == null) {
            if (h.free != null) {
                free = h.free
                h.free = null
            }
        } else {
            if (h.free != null) {
                insertPair(free!!, h.free!!)
                h.free = null
                free = null
            }
        }

        // set new sizes
        size += h.size
        h.size = 0

        // take ownership
        h.other = this
    }

    /**
     * Insert a pair of elements, one in the min heap and one in the max heap.
     *
     * @param handle1
     * a handle to the first element
     * @param handle2
     * a handle to the second element
     */
    private fun insertPair(handle1: ReflectedHandle<K, V>, handle2: ReflectedHandle<K, V>) {
        val c = comparator?.compare(handle1.key, handle2.key) ?: (handle1.key as Comparable<K>?)!!.compareTo(handle2.key)

        val innerHandle1: AddressableHeap.Handle<K, HandleMap<K, V>>
        val innerHandle2: AddressableHeap.Handle<K, HandleMap<K, V>>

        if (c <= 0) {
            innerHandle1 = minHeap.insert(handle1.key) as AddressableHeap.Handle<K, HandleMap<K, V>>
            handle1.minNotMax = true
            innerHandle2 = maxHeap.insert(handle2.key) as AddressableHeap.Handle<K, HandleMap<K, V>>
            handle2.minNotMax = false
        } else {
            innerHandle1 = maxHeap.insert(handle1.key) as AddressableHeap.Handle<K, HandleMap<K, V>>
            handle1.minNotMax = false
            innerHandle2 = minHeap.insert(handle2.key) as AddressableHeap.Handle<K, HandleMap<K, V>>
            handle2.minNotMax = true
        }
        handle1.inner = innerHandle1
        handle2.inner = innerHandle2

        innerHandle1.value = HandleMap(handle1, innerHandle2)
        innerHandle2.value = HandleMap(handle2, innerHandle1)
    }

    /**
     * Delete an element
     *
     * @param n
     * a handle to the element
     */
    private fun delete(n: ReflectedHandle<K, V>) {
        require(!(n.inner == null && free !== n)) { "Invalid handle!" }

        if (free === n) {
            free = null
        } else {
            // delete from inner queue
            val nInner = n.inner!!
            val nOuter = nInner.value!!.outer
            nInner.delete()
            nOuter.inner = null
            nOuter.minNotMax = false

            // delete pair from inner queue
            val otherInner = nInner.value!!.otherInner
            val otherOuter = otherInner.value!!.outer
            otherInner.delete()
            otherOuter.inner = null
            otherOuter.minNotMax = false

            // reinsert either as free or as pair with free
            if (free == null) {
                free = otherOuter
            } else {
                insertPair(otherOuter, free!!)
                free = null
            }
        }
        size--
    }

    /**
     * Decrease the key of an element.
     *
     * @param n
     * the element
     * @param newKey
     * the new key
     */
    private fun decreaseKey(n: ReflectedHandle<K, V>, newKey: K) {
        require(!(n.inner == null && free !== n)) { "Invalid handle!" }
        val c = comparator?.compare(newKey, n.key) ?: (newKey as Comparable<K>).compareTo(n.key)
        require(c <= 0) { "Keys can only be decreased!" }
        n.key = newKey
        if (c == 0 || free === n) {
            return
        }

        // actual decrease
        val nInner = n.inner
        if (n.minNotMax) {
            // we are in the min heap, easy case
            n.inner!!.decreaseKey(newKey)
        } else {
            // we are in the max heap, remove
            nInner!!.delete()
            val nOuter = nInner.value!!.outer
            nOuter.inner = null
            nOuter.minNotMax = false

            // remove min
            val minInner = nInner.value!!.otherInner
            val minOuter = minInner.value!!.outer
            minInner.delete()
            minOuter.inner = null
            minOuter.minNotMax = false

            // update key
            nOuter.key = newKey

            // reinsert both
            insertPair(nOuter, minOuter)
        }
    }

    /**
     * Increase the key of an element.
     *
     * @param n
     * the element
     * @param newKey
     * the new key
     */
    private fun increaseKey(n: ReflectedHandle<K, V>, newKey: K) {
        require(!(n.inner == null && free !== n)) { "Invalid handle!" }
        val c = comparator?.compare(newKey, n.key) ?: (newKey as Comparable<K>).compareTo(n.key)
        require(c >= 0) { "Keys can only be increased!" }
        n.key = newKey
        if (c == 0 || free === n) {
            return
        }

        // actual increase
        val nInner = n.inner
        if (!n.minNotMax) {
            // we are in the max heap, easy case
            n.inner!!.decreaseKey(newKey)
        } else {
            // we are in the min heap, remove
            nInner!!.delete()
            val nOuter = nInner.value!!.outer
            nOuter.inner = null
            nOuter.minNotMax = false

            // remove max
            val maxInner = nInner.value!!.otherInner
            val maxOuter = maxInner.value!!.outer
            maxInner.delete()
            maxOuter.inner = null
            maxOuter.minNotMax = false

            // update key
            nOuter.key = newKey

            // reinsert both
            insertPair(nOuter, maxOuter)
        }
    }

    // ~-------------------------------------------------------------------
    /*
     * This is the outer handle which we provide to the users.
     */
    /*
         * We maintain explicitly the belonging heap, instead of using an inner
         * class due to possible cascading melding.
         */
    class ReflectedHandle<K, V>(
          var heap: ReflectedHeap<K, V>,
          override var key: K,
          override var value: V?
    ) : DoubleEndedAddressableHeap.DoubleEndedHandle<K, V>, Serializable {
        /*
         * Whether the key is inside the minimum or the maximum heap (if not the
         * free element).
         */
        var minNotMax: Boolean = false

        /*
         * Handle inside one of the inner heaps, or null if free element.
         */
        var inner: AddressableHeap.Handle<K, HandleMap<K, V>>? = null

        /**
         * {@inheritDoc}
         */
        override fun decreaseKey(newKey: K) {
            owner.decreaseKey(this, newKey)
        }

        /**
         * {@inheritDoc}
         */
        override fun delete() {
            owner.delete(this)
        }

        /**
         * {@inheritDoc}
         */
        override fun increaseKey(newKey: K) {
            owner.increaseKey(this, newKey)
        }

        /*
        * Get the owner heap of the handle. This is union-find with
        * path-compression between heaps.
        */
        val owner: ReflectedHeap<K, V>
            get() {
                if (heap.other !== heap) {
                    // find root
                    var root = heap
                    while (root !== root.other) {
                        root = root.other
                    }
                    // path-compression
                    var cur = heap
                    while (cur.other !== root) {
                        val next = cur.other
                        cur.other = root
                        cur = next
                    }
                    heap = root
                }
                return heap
            }
    }

    /*
     * Value kept in the inner heaps, in order to map (a) to the outer heap and
     * (b) to the pair inside the other inner heap.
     */
    class HandleMap<K, V>(
        var outer: ReflectedHandle<K, V>,
        var otherInner: AddressableHeap.Handle<K, HandleMap<K, V>>
    ) : Serializable { }
    
}
